1. Field of Invention
The present invention relates generally to data communication systems. More particularly, the present invention relates to systems and methods for creating a primary path while effectively ensuring that an alternate path to the primary path is available.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. Furthermore, the types of traffic being carried by the Internet are shifting from lower bandwidth applications towards high bandwidth applications which include voice traffic and video traffic.
To address the demand for data communication services, the use of optical networks, such as a synchronous optical network (SONET), is becoming more prevalent. As will be appreciated by those skilled in the art, a SONET network is an example of a time division multiplexed (TDM) network. TDM networks generally allocate single lines to be used amongst multiple data streams or connections. The single lines may each be divided into slots of time during which each user has access to the single lines.
A network such as a TDM network is generally designed to ensure that information may be transferred between nodes within the network. Often, within a network, information is transferred between two specified nodes, i.e., a source node that sends information and a destination node which receives information. When information is to be sent between a source node and a destination node, a circuit path between the two nodes must be computed so that leased line services may be provided.
Often, to increase the likelihood that data will be successfully transferred, a circuit path between a source node and a destination node may be protected. A protected circuit path is a path which includes redundancy that generally allows data to be transferred even in the event of a nodal failure or a link failure. A protected circuit path may include protected links, e.g., links with ‘1+1’ protection, as will be appreciated by those skilled in the art. A protected circuit path may also include unprotected links, provided that there is a corresponding alternate circuit path associated with the unprotected links. An alternate circuit path effectively serves as a “back up” path to a primary circuit path which includes unprotected links in the event that the primary circuit path fails. For instance, when a primary circuit path suffers either a nodal failure or a failure of a link, data that was to be sent through the primary circuit path may be sent through the alternate circuit path instead. As some protected circuit paths may include both protected path segments and unprotected segments, some protected paths may include “partial” alternate path segments which correspond to the unprotected segments.
FIG. 1a is a diagrammatic representation of a portion of a network which includes nodes and unprotected links. Within a network portion 102, nodes 104 are connected to other nodes 104 through links 108. Information or data that is to be routed through portion 102 is routed from a source node 104a to a destination node 104d. As shown, using a routing algorithm such as a shortest path first (SPT) algorithm, a circuit path 112 between node 104a and node 104d may be created such that path 112 passes through node 104b and node 104c. 
When it is desired for circuit path 112 to be protected, since links 108 are unprotected links, an alternate path which corresponds to path 112 may be created after path 112 is created. The creation of an alternate path prevents a failure of a link 108 or a node 104 within path 112 from preventing the successful routing of data from node 104a to node 104d. In other words, an alternate path effectively provides protection for path 112, or primary path 112, which includes unprotected links 108. As shown, a protected path such as path 112 may include unprotected links, i.e., links 108, which may be protected using an alternate path which also includes unprotected links 108.
With reference to FIG. 1b, an alternate circuit path which corresponds to path 112, will be discussed. When an element within path 112 of FIG. 1a fails, e.g., when node 104b suffers a failure, data may be sent between node 104a and node 104d through an alternate path 116, which bypasses node 104b and node 104c which are a part of path 112. Alternatively, the data may be sent across both path 112 and alternate path 116 to node 104d, substantially simultaneously, such that node 104d may effectively select the data it wishes to receive. That is, when the data is sent across both path 112 and alternate path 116, node 104d may then determine if an element in path 112 has failed. If an element in path 112 has failed, then node 104d may elect to use the data received on alternate path 116. Alternate path 116 generally does not use nodes 104 or links 108 which are included in path 112, thereby enabling alternate path 116 to be both nodal diverse and link diverse with respect to path 112. That is, alternate path 116 is typically nodal diverse and link diverse. Hence, when a node 104 or a link 108, e.g., node 104b as shown, fails, alternate path 116 is substantially unaffected.
FIG. 1c is a diagrammatic representation of portion 102 which shows a circuit path 120 which allows data to be transferred from node 104a to a destination node 104h. As no alternate path is available for path 120, when an element of path 120 fails, data may not be transferred from node 104a to node 104h. For example, as shown in FIG. 1d, when node 104g fails, data may not be passed from node 104a to node 104h. 
As previously mentioned, when path protection is needed and only unprotected links are available for use in creating a path, it is preferable to have an alternate path exist for a corresponding primary path, since an alternate path may be used to allow data to be transmitted when a primary path fails. Typically, an alternate path is computed after the computation of a primary path. That is, after a primary path is routed, it is then determined whether it is possible to route an alternate path. If it is possible to route an alternate path, the alternate path is routed. Alternatively, in situations where it is not possible to route an alternate path, then an alternate path is not routed. In the event that protection is desired but an alternate path is not possible, an attempt may be made to create a different primary path which includes, for instance, protected links, as will be appreciated by those skilled in the art.
Creating an alternate path often uses a substantial amount of computational overhead, and may be time-consuming. When the result of an attempt to create an alternate path is successful, i.e., when an alternate path exists, then the alternate path is created, and the computational overhead and time associated with computing the alternate path is effectively not wasted. However, when there is no possible alternate path that corresponds to a given primary path, then the computational overhead and the time associated with attempting to create the alternate path is essentially wasted, as is the computational overhead and the time spent in determining the primary path. The computational overhead and time spent in determining the primary path may be considered as wasted, since when an alternate path is required, the failure to create an alternate path typically results in a need to route a new primary path. Once this new primary path is routed, then another attempt may be made to create a corresponding alternate path. Such a process is often relatively time-consuming and, as a result, inefficient.
Therefore, what is needed is a method and an apparatus for efficiently identifying alternate circuit paths that correspond to primary circuit paths. Specifically, what is desired is a system which effectively validates the existence of an alternate circuit path during the computation of a primary circuit path, before an attempt is made to route the alternate circuit path.